package data_structure.mooc;

import java.util.ArrayList;

public class AVLTree<K extends Comparable<K>,V> {


    //节点类
    private class Node{
        public K key;
        public V value;
        public Node left;
        public Node right;
        //引入高度
        public int height;

        public Node(K key,V value){
            this.key = key;
            this.value = value;
            this.left=null;
            this.right = null;
            height=1;
        }
    }
    private Node root;
    private int size;

    public AVLTree(){
        this.root=null;
        size=0;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public int getSize(){
        return size;
    }

    private int getHeight(Node node){
        if(node==null)return 0;
        return node.height;
    }

    private int getBalancedFactory(Node node){
        if(node==null)return 0;
        return getHeight (node.left)-getHeight (node.right);
    }

    public boolean isBST(){

        ArrayList<K>keys = new ArrayList<K> ();
        inOrder(root,keys);
        for(int i=1;i<keys.size ();i++){
            if(keys.get(i-1).compareTo (keys.get(i))>0)return false;
        }
        return true;
    }

    private void inOrder(Node node,ArrayList<K> keys){
        if(node==null)return;
        inOrder (node.left,keys);
        keys.add (node.key);
        inOrder (node.right,keys);
    }

    public boolean isBalanced(){
        return isBalanced (root);
    }

    private boolean isBalanced(Node node){
        if(node==null)return true;
        if(Math.abs (getBalancedFactory (node))>1)return false;
        return isBalanced (node.left)&&isBalanced(node.right);
    }
    public void add(K key,V value){
        root=add(root,key,value);
    }

    /**
     * node作为根节点，但是所在树不满足AVL特性，通过将node.left作为根节点，进行旋转,返回新的根节点
     * @param y
     * @return
     */
    private Node rightRotate(Node y){
        Node x=y.left;
        Node T3=x.right;
        x.right=y;
        y.left=T3;
        y.height=1+Math.max (getHeight (y.left),getHeight (y.right));
        x.height=1+Math.max(getHeight (x.left),getHeight (x.right));
        return x;
    }

    /**
     * 左旋转
     * @param y
     * @return
     */
    private Node leftRotate(Node y){

        Node x=y.right;
        Node T3=x.left;
        x.left=y;
        y.right=T3;
        y.height=1+Math.max (getHeight (y.left),getHeight (y.right));
        x.height=1+Math.max(getHeight (x.left),getHeight (x.right));
        return x;
    }
    /**
     * 向根节点为node添加元素，返回添加元素之后AVL树的根节点
     * @param node
     * @param key
     * @param value
     * @return
     */
    private Node add(Node node,K key, V value){
        if(node==null){
            size++;
           return new Node(key, value);
        }

        //添加元素
        if(key.compareTo (node.key)<0){
            node.left=add(node.left,key,value);
        }else if(key.compareTo(node.key) > 0){
            node.right=add(node.right,key,value);
        }else{//key==node.key
            node.value=value;
        }
        //更新高度
        node.height=Math.max (getHeight (node.left),getHeight(node.right))+1;
        //平衡因子
        int balanceFactory=getBalancedFactory (node);
        //平衡操作
        //LL
        if(balanceFactory>1&&getBalancedFactory (node.left)>=0){
            return rightRotate (node);
        }
        //RR
        if(balanceFactory<-1&&getBalancedFactory (node.right)<=0){
            return leftRotate (node);
        }
        //LR
        if(balanceFactory > 1 && getBalancedFactory(node.left)<0){
            node.left=leftRotate (node.left);
            return rightRotate (node);
        }
        //RL
        if(balanceFactory<-1&&getBalancedFactory (node.right)>0){
            node.right=rightRotate (node.right);
            return leftRotate (node);
        }
        return node;
    }

    private Node minNode(Node node){
        Node curr=node;
        while(curr.left!=null){
            curr = curr.left;
        }
        return curr;
    }

    /**
     * 返回删除最小节点后的根节点
     * @param node
     * @return
     */
    private Node removeMin(Node node){

        if(node.left==null){
            Node rightNode=node.right;
            node.right=null;
            size--;
            return rightNode;
        }
        node.left = removeMin (node.left);
        return node;
    }

    /**
     * 删除操作
     * @param key
     * @return
     */
    public V remove(K key) {

        Node del=getNode (root,key);
        if(del == null)return null;
        else{
            return remove (root,key).value;
        }
    }
    /**
     * 在根节点为node的树中删除key所在的节点，返回删除节点之后的根节点
     * @param node
     * @param key
     * @return
     */
    private Node remove(Node node,K key){

        if(node==null){
            return null;
        }
        Node retNode;
        if(key.compareTo (node.key)<0){
            node.left=remove(node.left, key);
            retNode= node;
        }else if (key.compareTo(node.key) > 0){
            node.right = remove(node.right, key);
            retNode= node;
        }else{
            if(node.left==null){
                Node rightNode=node.right;
                node.right=null;
                size--;
                retNode= rightNode;
            }else if(node.right == null){
                Node leftNode=node.left;
                node.left=null;
                size--;
                retNode= leftNode;
            }else{
                Node successor=minNode (node.right);
                //attention:
                //和BSTMap作比较
                Node rightNode=remove (node.right,successor.key);
                successor.left=node.left;
                successor.right=rightNode;
                node.left=node.right=null;
                retNode= successor;
            }
        }
        if(retNode==null)return null;
        //平衡操作

         //更新高度
        retNode.height=Math.max (getHeight (retNode.left),getHeight(retNode.right))+1;
        //平衡因子
        int balanceFactory=getBalancedFactory (retNode);
        //平衡操作
        //LL
        if(balanceFactory>1&&getBalancedFactory (retNode.left)>=0){
            return rightRotate (retNode);
        }
        //RR
        if(balanceFactory<-1&&getBalancedFactory (retNode.right)<=0){
            return leftRotate (retNode);
        }
        //LR
        if(balanceFactory > 1 && getBalancedFactory(retNode.left)<0){
            retNode.left=leftRotate (retNode.left);
            return rightRotate (retNode);
        }
        //RL
        if(balanceFactory<-1&&getBalancedFactory (retNode.right)>0){
            retNode.right=rightRotate (retNode.right);
            return leftRotate (retNode);
        }
        return retNode;
    }

    private Node getNode(Node node,K key){

        if (node == null) {
            return null;
        }
        if(key.compareTo (node.key)<0){
            return getNode (node.left,key);
        }else if(key.compareTo (node.key)>0){
            return getNode(node.right, key);
        }
        return node;
    }

     public void set(K key, V newValue) {
        Node node = getNode(root, key);
        if(node==null){
            throw new IllegalArgumentException (key+"doesn't exit");
        }
        node.value = newValue;
    }

    public V get(K key){
        if(!contains (key))throw new IllegalArgumentException(key+"does't exit");
        return getNode(root, key).value;
    }

    public boolean contains(K key){
        return getNode (root,key)!=null;
    }
}
